package 代码题.动态规划题目;

/**
 * 完全背包问题
 * <p>
 * 同样是一个背包，多个物品，每个物品都有价值和重量，但是这里每个物品可以存放多次
 * <p>
 * 思路：尽可能买体积小的
 * 状态转移方程：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - k * weight[i]] + k * value[i]);
 * dp[i][j]表示的是在容量为j的情况下选取第i个物品的最大value值
 *
 * 这里是3重循环，最内层的循环，是常识将当前物品进行多次放入
 */
public class DP_ALL {

    /**
     * 一个背包，20的重量
     * 4个物品，每个物品的价值和重量的键值对为
     * (7,3),(5,2),(6,4),(9,5)
     * <p>
     * 输出结果：50。表示买10个第2物品
     *
     * @param args
     */
    public static void main(String[] args) {
        int[][] dp = new int[5][21];  //默认初始化二维数组为0.需要增加一个辅助行和辅助列
        int[] value = new int[]{0, 7, 5, 6, 9};
        int[] weight = new int[]{0, 3, 2, 4, 5};

        for (int i = 1; i < 5; i++) {
            for (int j = 1; j < 21; j++) {

                for (int k = 0; k * weight[i] <= j; k++) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - k * weight[i]] + k * value[i]);
                }

            }
        }
        System.out.println(dp[4][20]);

        //打印最值得二维数组
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 21; j++) {
                System.out.print(dp[i][j]+"\t");
            }
            System.out.println();
        }
    }
}
